// https://leetcode.cn/problems/counting-bits
class Solution {
public:
    vector<int> countBits(int n) {
        // 暴力遍历, 每个数判断一下1的个数
        vector<int> ret(n + 1, 0);
        for(int i = 0; i <= n; i++) {
            int count = 0, tmp = i;
            while(tmp) {
                tmp &= (tmp - 1); // 干掉最右侧的1
                count++;
            }
            ret[i] = count;
        }
        return ret;
    }
};
